home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / c / bchelp10.zip / TI398.ASC < prev    next >
Text File  |  1991-09-11  |  4KB  |  199 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.   PRODUCT  :  TURBO C                                NUMBER  :  398
  9.   VERSION  :  1.0
  10.        OS  :  PC-DOS
  11.      DATE  :  January 6, 1988                          PAGE  :  1/3
  12.  
  13.     TITLE  :  QSORT
  14.  
  15.  
  16.  
  17.  
  18.   qsort  is  an  implementation  of  the  Quicksort  algorithm  and
  19.   requires four parameters:   the  array to sort, the length of the
  20.   array, the width of the array, and a comparison function.
  21.  
  22.   qsort 's length and width parameters are  fairly straightforward.
  23.   If you are sorting an array declared as:
  24.  
  25.               int array[100];
  26.  
  27.   the  length  of the array is 100 and the width of  the  array  is
  28.   "sizeof(int)".   Generally, the length and width of any array can
  29.   be  expressed as:  "sizeof(array)/sizeof(array[0])" (the size  of
  30.   array divided by  the  size  of  the first element of array), and
  31.   "sizeof(array[0])" (the  size  of  the  first  element  of array)
  32.   respectively.
  33.  
  34.   The fourth parameter (the comparison routine) usually  causes the
  35.   most  trouble.    The  reference  guide  states  that the  fourth
  36.   parameter is a pointer to a  function.   This means that you must
  37.   give  the name of a routine as the  fourth  parameter;  you  must
  38.   supply this routine yourself.
  39.  
  40.   qsort will call your  routine  to  do  all comparisons.  Pointers
  41.   will be passed to the array elements which are  to  be  compared.
  42.   You do not  have  to  be  concerned  how this is done, qsort will
  43.   handle this for you.  Your routine must return  an  integer,  the
  44.   value of which will be:
  45.  
  46.     positive   -  if the first element is greater than the second.
  47.  
  48.             0  -  if the elements are equal.
  49.  
  50.     negative   -  if the second element is greater than the first.
  51.  
  52.   To sort the above array in ascending order, the routine is:
  53.  
  54.   int fcmp(int *num1, int *num2)
  55.   {
  56.       return (*num1 - *num2);
  57.   }
  58.  
  59.   qsort can  also  sort  arrays  of  structures.   If the array was
  60.   defined:
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.   PRODUCT  :  TURBO C                                NUMBER  :  398
  75.   VERSION  :  1.0
  76.        OS  :  PC-DOS
  77.      DATE  :  January 6, 1988                          PAGE  :  2/3
  78.  
  79.     TITLE  :  QSORT
  80.  
  81.  
  82.  
  83.  
  84.   struct address
  85.   {
  86.       char LastName[16];
  87.       char FirstName[11];
  88.       char Street[30];
  89.       char City[21];
  90.       char State[3];
  91.       char Zip[6];
  92.   } AddressBook[100];
  93.  
  94.   To sort "AddressBook" on "LastName" the fcmp routine would be:
  95.  
  96.   int fcmp(struct address *first, struct address *second)
  97.   {
  98.       return (strcmp(first->LastName,second->LastName));
  99.   }
  100.  
  101.   To  sort the same array on "Zip" in  the  above  routine,  simply
  102.   change "LastName" to "Zip".  The call to qsort for  both examples
  103.   would look like:
  104.  
  105.     qsort(AddressBook, sizeof(AddressBook)/sizeof(AddressBook[0]),
  106.            sizeof(AddressBook[0]), fcmp);
  107.  
  108.   The best way to put this all together is a sample program.
  109.  
  110.   /* The program will generate 100 random numbers.  Store them
  111.    * in an array.  Print them out.  Call qsort to sort them
  112.    * and print them out again.
  113.    */
  114.  
  115.   #include <stdio.h>
  116.   #include <stdlib.h>
  117.   #include <time.h>
  118.  
  119.   #define ARRAYLEN 100
  120.  
  121.   int array[ARRAYLEN];       /* Array to sort */
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.   PRODUCT  :  TURBO C                                NUMBER  :  398
  141.   VERSION  :  1.0
  142.        OS  :  PC-DOS
  143.      DATE  :  January 6, 1988                          PAGE  :  3/3
  144.  
  145.     TITLE  :  QSORT
  146.  
  147.  
  148.  
  149.  
  150.   /* Comparison routine passed to and used by qsort() */
  151.   int fcmp(int *num1, int *num2)
  152.   {
  153.       return (*num1 - *num2);
  154.   }
  155.  
  156.   main()
  157.   {
  158.      long along;
  159.      int i;
  160.  
  161.      /* Seed the random number generator */
  162.      srand((unsigned) time(&along));
  163.      for (i=0; i<ARRAYLEN; i++)
  164.          array[i] = rand() % ARRAYLEN;
  165.  
  166.      /* Print the random array */
  167.      printf("\nOriginal array\n");
  168.      for (i=0; i<ARRAYLEN; i++)
  169.      {
  170.          printf("%4d ",array[i]);
  171.          if ( !((i+1) % 15) )
  172.              putchar('\n');
  173.      }
  174.  
  175.      /* Call qsort() */
  176.     qsort(array,sizeof(array)/sizeof(*array),sizeof(*array),fcmp);
  177.  
  178.      /* Print the sorted array */
  179.      printf("\n\nSorted array\n");
  180.      for (i=0; i<ARRAYLEN; i++)
  181.      {
  182.          printf("%4d ",array[i]);
  183.          if ( !((i+1) % 15) )
  184.              putchar('\n');
  185.      }
  186.   }
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.